Lý thuyết thông tin thuật toán chủ yếu nghiên cứu các biện pháp phức tạp trên các chuỗi (hoặc các cấu trúc dữ liệu khác). Bởi vì hầu hết các đối tượng toán học có thể được mô tả dưới dạng chuỗi hoặc là giới hạn của chuỗi chuỗi, nên nó có thể được sử dụng để nghiên cứu nhiều loại đối tượng toán học, bao gồm cả số nguyên.

Một cách không chính thức, từ quan điểm của lý thuyết thông tin thuật toán, nội dung thông tin của một chuỗi tương đương với độ dài của biểu diễn tự chứa có thể nén nhất của chuỗi đó. Một đại diện khép kín về cơ bản là một chương trình, trong một số ngôn ngữ lập trình phổ quát cố định nhưng không liên quan, thì khi chạy, sẽ xuất ra chuỗi gốc.

Từ quan điểm này, một bách khoa toàn thư 3000 trang thực sự chứa ít thông tin hơn 3000 trang của các chữ cái hoàn toàn ngẫu nhiên, mặc dù thực tế là bách khoa toàn thư hữu ích hơn nhiều. Điều này là do để xây dựng lại toàn bộ chuỗi các chữ cái ngẫu nhiên, người ta phải biết, ít nhiều, mỗi chữ cái là gì. Mặt khác, nếu mọi nguyên âm được loại bỏ khỏi bách khoa toàn thư, một người có kiến thức hợp lý về ngôn ngữ tiếng Anh có thể tái tạo lại nó, giống như người Anh có thể tái tạo lại câu "Ths sntnc hs lw nfrmtn cntnt" từ ngữ cảnh và phụ âm.

Không giống như lý thuyết thông tin cổ điển, lý thuyết thông tin thuật toán đưa ra các định nghĩa chính thức, nghiêm ngặt về một chuỗi ngẫu nhiên và một chuỗi vô hạn ngẫu nhiên không phụ thuộc vào trực giác vật lý hoặc triết học về thuyết không xác định hoặc khả năng. (Tập hợp các chuỗi ngẫu nhiên phụ thuộc vào sự lựa chọn của máy Turing phổ dụng được sử dụng để xác định độ phức tạp Kolmogorov, nhưng bất kỳ lựa chọn nào cũng cho kết quả tiệm cận giống hệt nhau vì độ phức tạp Kolmogorov của chuỗi là bất biến phụ thuộc vào hằng số phụ thuộc máy móc. Vì lý do này, tập hợp các chuỗi vô hạn ngẫu nhiên không phụ thuộc vào sự lựa chọn của máy vạn năng.)

Một số kết quả của lý thuyết thông tin thuật toán, chẳng hạn như định lý không hoàn chỉnh của Chaitin, dường như thách thức các trực giác toán học và triết học phổ biến. Đáng chú ý nhất trong số này là việc xây dựng liên tục Chaitin của Ω, một số thực mà diễn tả xác suất mà một máy Turing phổ tự phân chia ranh giới sẽ ngừng khi đầu vào của nó được cung cấp bởi flips một xu công bằng (đôi khi coi là xác suất mà một ngẫu nhiên chương trình máy tính cuối cùng sẽ dừng lại). Mặc dù Ω có thể dễ dàng xác định, trong bất kỳ phù hợp axiomatizable lý thuyết duy nhất có thể tính hữu hạn nhiều chữ số của Ω, vì vậy nó là ở một số cảm giác không thể biết, cung cấp một giới hạn tuyệt đối về kiến thức đó là gợi nhớ đến không đầy đủ Định lý Gödel. Mặc dù các chữ số của Ω không thể được xác định, nhiều tài sản của Ω được biết; ví dụ, nó là một chuỗi ngẫu nhiên theo thuật toán và do đó các chữ số nhị phân của nó được phân bố đều (thực tế nó là bình thường).